It is widely recognized that verification of modem hardware design involves an effort comparable to that invested in the design itself. For complex designs, elaborate testcases aimed at confirming the functional correctness of the design are necessary. Naturally, smaller and less complex units are simpler to verify, and the results of their verification can be accepted with greater confidence than in more complex cases. Therefore, in a system composed of a number of components, it is always beneficial to commit to a complete, independent, verification effort for each of the constituent components. However, there are three reasons why, in general, it is not sufficient to limit verification testing to the component level, and why verification of the system as a whole should also be performed:
First, it may happen that while each of the constituents of the system behaves according to specification, there is still a mismatch between the interfaces of two interacting components in the system. For example, two components may send concurrent signals to two ports of a third component, but the latter may have a specification that allows accepting signals at only one port at a time.
Second, it is often difficult to artificially generate stimuli that cover the entire specification of a complex component. For example, building a bus behavioral for a complex interface that generates all possible packet types is a large and expensive task. It may therefore be preferable to verify some aspects of a units behavior some packet types in the present example only as part of the entire system, in which the complex interface is stimulated by other real units of the system.
Third, in practice, the stimuli generated by a real system may have different characteristics from artificially-generated stimuli, and this difference may be impossible to predict. Verifying a unit in the context of the real system may therefore uncover design flaws that otherwise would escape detection.
System-level testing is accomplished by generating sets of system-level transactions that exercise the complete system as a whole. The entire space of possible system-level transactions is typically extremely large, and it is therefore possible to test only a very small, and necessarily restricted portion of this space. In order for a verification plan having such a restricted set of test transactions to be meaningful, the tests must be diverse enough to stimulate all significant logical areas of the design under test, while at the same time being specific enough to stress particular logical areas that are prone to error. A typical way of handling this is to use an automated test-program generator for randomly creating tests that stimulate the system according to the foregoing guidelines.
System-level transactions must be scheduled in a particular manner, because the outcome of any set of transactions may depend critically on the sequence. There are, however, three general problems in scheduling the transactions for system-level verification:                1. System-level transactions are high-level entities whose start and end times are often not well-defined. It is therefore not a priori evident what types of transaction-scheduling scenarios are even possible.        2. It is not evident how to request transaction-scheduling scenarios on top of other test-generator requests, which are generally aimed at stressing specific logical areas of the design under test. To optimize the randomness of the test, transaction-scheduling scenarios should be allowed to remain unspecified when not explicitly required to be specified. The term partial specification herein designates the ability to leave some transaction-scheduling parameters unspecified in a test-generation environment.        3. An algorithm for scheduling many transactions is sometimes necessary to achieve a particular aspect of the test-plan, but a simple general algorithm for this does not yet exist.        
FIG. 1 shows a model-based test-program generator 101 which accepts user-defined requests from a request file 107, and generates a testcase 109 which realizes request file 107 so that testcase 109 contains program code which fulfills the requests in request file 107 at the system level. Test-program generator 101 contains a system-specific system model 103 which describes the components, topology, and available transactions of the system to be exercised. System model 103 and request file 107 are input into a testcase engine 105, which outputs testcase 109. Testcase 109 is then used to stimulate the system for verification purposes. In general, repeated operation of test-program generator 109 for a given request file results in different valid testcases, and in this manner a suite of testcases can be generated. In addition to strict modeling of the specified behavior of each component under the various transactions, system model 103 may also include testing knowledge about the system that is not part of the hardware specification, but is believed to help direct test-program generator 101 in creating more interesting and meaningful tests.
Note that a set of transactions used in test-program generation may not be complete, and a system for generating test programs should support the addition of new transactions to the model.
Much of a test-program generators success in achieving the verification goals depends on the capabilities of the request file language. In particular, this language should be able to express in a natural way which types of transactions are to be generated by the generator for a particular set of tests, and which parameters are to be used with those transactions. The language should also allow for stressing a particular logical area of the design. Finally, the language must allow for partial specification in the request file, meaning that the user need not specify all parameters related to the test. Parameters not specified by the user are determined by the test-program generator, either randomly or according to testing knowledge.
Component versus Transaction View
When designing the semantics of the request language, there are two ways of viewing the system under verification. The first way is the component view, in which the language focuses separately on each of the components in the system. Interactions between components are treated merely as required for establishing the events stimulating the verified component. As an example, FIG. 2 illustrates a system 201 in which a set of processors 203 are connected through sets of busses 205, 213, and 217 and sets of bus bridges 207, 215, and 219 to a set of bus-behaviorals 221 that model, for example, I/O devices, as well as to shared resources, such as a set of memories 211 connected via a set of busses 209.
In the example presented above, a request language based on the component view might include a request such as:
P1 executing 500 load/store transactions
Such a view is necessarily centered on the components that initiate transactions, such as processors 203 and sometimes I/O behaviorals 221. Consequently, it is difficult and unnatural to specify a request centered at P1 (for example) in a way that would reflect the verification needs of the interaction between B11 and B21. In addition, when the system is symmetric with respect to some of the components, there is usually no purpose in specifying which of the components should participate in any given task, but such a specification is inherent in the component view. This over-specification unnecessarily reduces the randomness of a generated test.
A second possible view of a system with many components is the transaction view. Here, the emphasis is on the transactions that take place in the system, where each transaction involves a number of different components. By focusing on transactions, the test-plan inherently acknowledges that a component in a complex environment is never verified independently. Therefore, when designing a language consistent with this view, significant attention must be put into identifying the way components interact with one another.
To design such a language, it is necessary to define, for each unique manner of system interaction, a transaction that involves all components of that system interaction. The language then uses these definitions to express constructs such as:
500 I/O-to-Mem DMA where DMA stands for Direct Memory Access, a manner of system interaction which, in the example above, has transactions that involve I/O and memory. In this notation, transactions are named by concatenating the transactions initiator components (I/O), the transactions target components (Mem), and the operation done by the transaction (DMA), thus I/O-to-Mem-DMA.
The advantage of expressing actions in this manner is that the user is not concerned about how to stimulate an end-component (an I/O behavioral in the case of a DMA transaction) in order to produce favorable stimuli on one of the bus-bridges. This task is left for the generator. The user can specify, however, certain characteristics of each transaction. These may include, for instance, the specific type of stimuli on a particular bus-bridge.
Nevertheless, even in the transaction view, each component should still be allowed to be stressed by the testcase in order to increase the probability of finding bugs in the behavior of that component. To do so, the language allows expressions such as 300 CPU-to-I/O-MMIO transactions all originating at P3, but terminating at any one of M1 M24, chosen at random, and an additional 200 CPU-to-Mem-Data-Transfer all from P3, but going to either MEM1 or MEM2,
where MMIO stands for Memory Mapped I/O.
Again, this scheme has the advantage of stressing P3 not merely by random read/write access, but by access which may span a wider logical area of the system.
Transactions and Transaction-Scheduling
A random test program for the system-level has two complementary aspects: the set of transactions contained by the test program, and the scheduling, or sequence ordering, of those transactions. Prior art approaches typically neglect transaction-scheduling. However, neglecting transaction-scheduling, as, well as not allowing freedom in specifying the transaction-scheduling, leads to limitations in the prior art. There are a number of advantages to be gained by having control over transaction-scheduling requests.
Most important, by requesting that some transactions be scheduled in a particular order, or be otherwise regulated with respect to their timing, it is possible to explore specific logical areas that are prone to bugs. In particular, some design bugs may show up only when transactions occur in a specific order, are separated by a specific time interval, or are executed concurrently. This is especially true when the transactions are initiated by different components that access a common resource. There are other reasons related to the mechanism of test-generation for scheduling transaction requests: In general, requesting a definite order of transactions allows more flexibility in other types of user requests and allows a more accurate prediction of the final state of the system. For example, when two processors write to the same address, it is impossible to predict the data stored in that address at the end of the test unless the order of the write transactions is known.
Existing Test-Program Generator Languages
Many prior-art languages are capable of specifying time relations between various events, but there is no prior art language or formalism applicable to the scheduling of system-level test transactions. Hence, the prior art necessarily lacks a comprehensive and efficient transaction scheduler, and thus prior-art test-program generators are unable to process any system-level transaction-scheduling requests. At the root of this limitation is the lack of a language capable of expressing the various aspects of transaction-scheduling. Thus, it is useful to first consider the question of a formal language for describing and prescribing system-level transactions.
As is shown below, the fact that system-level transactions are high-level entities means that a language suitable for this task must have restrictions in the ability to express the timing relationships of transactions. In addition, if the language is to be useful in the context of test generation, there are other necessary attributes, such as the ability to express ordering between large groupings of transactions.
Examples of existing languages that have temporal constructs range from Java to temporal logic. A few of the representative languages are relevant to system-level transactions and test generation. An article by L. Lamport On interprocess communication, Distributed Computing, 1:76101, 1986 (herein referred to as Lamport) discloses a temporal language dealing with high-level transactions that has no notion of true time. Another example of a prior-art formalism partially-relevant to the area of interest is that of Interacting Processes (IP), which is based on standard constructs in applications-programming languages and operating systems which deal with concurrent asynchronous processes (such as threads). IP is a process-synchronizing language designed for programming specific scenarios in a multi-process environment, but is not suitable for generating test programs or for scheduling transactions in a test program. A further example of a prior art formalism that addresses similar issues has been presented by D. Harel in: StateCharts: A visual formalism for complex systems [Science of Computer Programming, 8(3):231 274, June 1987], which deals with general concurrent systems. There are significant difficulties in using such languages (as well as other temporal languages) for describing and specifying test-program generator requests, most notably in being unable to express partial specifications. The formalisms underlying these prior-art languages have no provision for randomness in the ordering of transactions. The ability to inject selective randomness into a test program is highly desirable, and a test-program generator with this ability is herein denoted as a random test-program generator. It is emphasized, however, that this ability may be selectively applied, and a random test-program generator is not restricted from producing completely deterministic output where desired.
Other problems with these languages also arise. IP requests are assigned to various processes in the system. The processes execute requests sequentially, but when a process encounters a synchronization request, that process waits and synchronizes with other processes according to specific constructs of the language. The language describes relationships between events in the time-line of each process, and is thus clearly based on the component view. StateCharts, for example, is a compact graphical language expressing various state-machine operations, and is designed to deal with concurrent events. However, StateCharts does not handle the issue of transaction-scheduling, and it has not been possible to combine a language of this type with other (non-scheduling) features necessary in a general test-generator request language.
Finally, it is noted that a methodology for system-verification using a non-model-based test-program generator was presented by D. Geist, G. Biran, T. Arons, M. Slavkin, Y. Nustov, M. Farkash, K. Holtz, A. Long, D. King, and S. Barret in A methodology for the verification of a system on chip (36th Design Automation Conference, DAC99, pages 574–579, 1999). This methodology also relies on the transaction view of the system, but the issue of transaction-scheduling is not disclosed in the cited publication.
There is thus a need for, and it would be highly advantageous to have, a test-generator which provides for scheduling transactions in system-level test generation, including an appropriate descriptive and prescriptive language. This goal is met by the present invention.